package com.example.javamaday.leetcode.sort;

// 希尔排序 （进阶版 插入排序）
public class LcSort0912_06 {

    public static void main(String[] args) {

    }

    public int[] sortArray(int[] nums) {
        int length = nums.length;
        // 确定增长量的最大值
        int h = 1;
        while (h < length / 2) {
            h = h * 2 + 1;
        }
        // 当增长量小于1的时候，跳出循环
        while (h >= 1) {
            for (int i = h; i < length; i++) {
                for (int j = i; j >= h; j -= h) {
                    if (nums[j - h] > nums[j]) {
                        exchange(nums, j - h, j);
                    } else {
                        break;
                    }
                }
            }
            h /= 2;
        }
        return nums;
    }

    public void exchange(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

}
